#include "BDD.h"


int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}



int createList(struct vertex* v,LinkedList *llist,int i, int var) 
{ 


	v->mark = !(v->mark);

//Insert vertex into list
//	vlist[i].u = v;
//	vlist[i].index = v->index;
//	vlist++;


//You can remove v->index from Node structure


	AddLast( &(llist[(v->index)-1]), v->index, v );				// -1 has done because its 0...n not i to n+1 
	i++;
	if((v->index) <= (var-1) )			//rigtht now i am inserting value for variables manually.
	{
		if((v->mark) != (v->low->mark))
			i = createList(v->low, llist, i, var);

		if ((v->mark) != (v->high->mark))
			i = createList(v->high,llist, i,var);

	}

	return i;
}







void reduction(graph *g, int var)
{
	int node, nextid,j,i =0,temp_int,k,itr;
	Node *temp;
	node =  graphSize(g, var);
	LinkedList llist[var];
	struct vertex *tempV;
	long nodes;

	
/* Dont make Q a linked list as it will be troublesome when u want to SORT it
	LinkedList Q;
*/

//Assuming that maximum node at a index can be 2^n-1. Dont know true or not
	nodes = pow(2,var);
	Set Q[nodes],oldkey,*T = NULL;
	
	for(;i<var;i++)
		Init ( &(llist[i]) ) ;

//	list vlist[node];

	vertex *subgraph[nodes+1];
	for(itr = 0;itr <node+1; itr++)
		subgraph[itr] = NULL;

	printf("No of nodes are %d\n", graphSize(g, var));

// put each vertex u on list vlist[u.index]:::: Here vlist is llist.

	createList(g->root, llist, i, var);

// nextid =0;
	
	nextid = 0;


//for  i := n+1 downto 1 do


	for (i=(var-1); i>=0; i-- )
	{
		//Q = Empty set	
		j=0;  // Here I have used j to keep track of how many nodes are thare at perticular index.
		

		temp = llist[i].head;

	//for each u in vlist[i] do 	
		while (temp != NULL)
		{
			//if u.index = n+1 
			if(temp->vert->index == var)
			{
				//then add<key,u> to Q where key = (u.value)
				Q[j].key1 = temp->vert->value;
				Q[j].key2 = temp->vert->value;
				Q[j].v = temp->vert;
				j++;
			}
			else{
				if(temp->vert->low->id == temp->vert->high->id)
					temp->vert->id = temp->vert->low->id;
				else {
					Q[j].key1 = temp->vert->low->id;
					Q[j].key2 = temp->vert->high->id;
					Q[j].v = temp->vert;
					j++;
				}
			}
			temp = temp ->link;
		}


	// Sorting elements of Q by key



	T = (Set *)binarySort(Q,j);

	for(k = 0; k<j; k++)
	{
		printf("%d and %d and %s\n",T[k].key1, T[k].key2, T[k].v->c);
	}	

	// oldkey =(-1,-1); {unmatched key}
		oldkey.key1 = -1;
		oldkey.key2 = -1;
		oldkey.v = NULL;

	//for each <key,u> in Q removed in order do
		for(k=0; k<j;k++)
		{	
			//if key=oldkey
			//	then u.id = nextid
			if(( T[k].key1 == oldkey.key1) && (T[k].key2 == oldkey.key2))
				T[k].v->id = nextid;
			else
			{
				nextid++;
				T[k].v->id = nextid;
				subgraph[nextid] = T[k].v;
				if( T[k].v->low != NULL)
					T[k].v->low = subgraph[ T[k].v->low->id];
				if( T[k].v->high != NULL)
					T[k].v->high = subgraph[T[k].v->high->id] ;
				oldkey.key1 = T[k].key1;
				oldkey.key2 = T[k].key2;
			}	

		}
	
	}

	printf("No of nodes are %d\n", graphSize(g, var));
}
